/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    // 归并排序做法
    /*
    ListNode* Merge(ListNode* p1, ListNode* p2) {
        ListNode* dummy = new ListNode(-1);
        ListNode* cur = dummy;
        while(p1 && p2) {
            if(p1->val < p2->val) {
                cur->next =p1;
                p1=p1->next;
                cur = cur ->next;
            }
            else {
                cur->next =p2;
                p2=p2->next;
                cur = cur ->next;
            }
        }
        if(p1) cur->next = p1;
        else if(p2) cur->next = p2;
        return dummy->next;
    }
    */
    // 递归
    ListNode* Merge(ListNode* p1, ListNode* p2) {
        if(!p1) return p2;
        if(!p2) return p1;
        if(p1->val < p2->val) {
            p1->next = Merge(p1->next, p2);
            return p1;
        }
        else {
            p2->next = Merge(p1, p2->next);
            return p2;
        }
        
        
        
        
    }
    
};